package org.yimon.tool.algo.leetcode;

/**
 * @Author yimon.gao
 * @Description 两数相加
 * @Date 2024/7/22 下午6:58
 */
public class LeetCode_002_AddTwoNumbers {

    public static void main(String[] args) {
        System.out.println(LeetCode_002_AddTwoNumbers.addTwoNumbers(new ListNode(2, new ListNode(4, new ListNode(3))), new ListNode(5, new ListNode(6, new ListNode(4)))));
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //特殊情况判读
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode next = new ListNode(0);//记录每次累加的结果
        ListNode result = next;//记录答案
        int carry = 0;//记录加法进位情况
        //双指针开始遍历l1、l2
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            //求和
            int sum = a + b + carry;
            next.next = new ListNode(sum % 10);//记录当前节点
            next = next.next;
            carry = sum / 10;//记录进位
            //继续下个节点遍历
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if (carry > 0) { //将进位加入节点
            next.next = new ListNode(carry);
        }
        return result.next;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
